1. Field of the Invention
The present invention relates generally to the field of computer systems. More particularly, the present invention relates to the field of random number generators for use by computer systems.
2. Description of Related Art
Random number generators may be used for a variety of electronic applications, such as lotteries, gambling machines, video games, image processing and reconstruction, music and graphics composition, scientific and financial modeling simulation, program and algorithm testing, equation-solving, and computer security for example. For computer security applications such as cryptography, digital signatures, and protected communication protocols, for example, random numbers are a fundamental building block for strengthening and securing the confidentiality of electronic communications.
Cryptography is the art and science of keeping messages secure and involves authentication, confidentiality, and integrity.
Authentication involves ensuring each entity communicating with one another is who the other entity or entities think it is. For an exemplary authentication protocol, a client requests access over a network to password protected information stored on a server. The server responds with a random challenge, such as a random number possibly combined with other information. The client encrypts the random challenge using its password as a key and returns the encrypted challenge to the server. The server encrypts the same random challenge with the client's password which the server obtains from its own password database. The server compares the two results. If the results match, the server has authenticated the client without the client ever sending its password over the network. Random number generation is therefore critical to help ensure no unauthorized entity observing an encrypted random challenge can impersonate the client by similarly responding to new random challenges.
Confidentiality involves ensuring that no unauthorized entity listening to a communication is able to extract meaningful information. Confidentiality is typically provided through data encryption which is the process of combining the original message with a cryptographic key in a well-defined manner to encrypt the message. In an ideal cryptosystem, only an entity with a decryption key can decrypt the encrypted message. By ensuring that the decryption key cannot be predicted or replicated and that only the intended recipient of the message has the required decryption key, the message can be protected from observation by an unauthorized entity. Cryptographic keys can be symmetric or asymmetric. Symmetric keys are used for both encrypting and decrypting data. Asymmetric keys are produced in pairs, each pair consisting of a public key to encrypt data and a private key to decrypt data. The strength of a cryptosystem lies in the strength of the key which is a function of not only the number of bits in the key but also the randomness of the number used to generate the key. Random number generation is therefore critical to help ensure the confidentiality of a message.
Integrity involves ensuring no undetected changes are made to a communication. Digital signatures help maintain the integrity of a message. A digital signature is a fixed-length binary string unique to a given message and signed with a private key. The unique string is known as a message digest or cryptographic hash. Because the unique string is signed with the originator's private key, any entity with the originator's public key can decrypt the message and know the owner of the private key originated the message. By generating another hash of the message using the same hashing algorithm as the originator and comparing the new hash with the signed hash, the recipient can verify that the message did not change after leaving the originator. Random number generation is critical to the strength of a signature generated using random numbers to avoid forgery of the signature.
Random numbers are a sequence of independent numbers with a specified distribution and a specified probability of falling in any given range of values. An ideal random number generator provides a stream of uniformly distributed, non-deterministic, independent bits over an infinite data set.
Typical computer programs use software random number generators as a random number generator may then be added to a computer system with relative ease. Software random number generators typically require a seed which is used as an operand in a mathematical algorithm to create a random number. The sequence of numbers generated by such software random number generators will eventually repeat, however, and are therefore better characterized as pseudo random numbers. Incorporating randomness into the seed and using sufficiently long mathematical computations help to generate numbers with relatively more randomness. Typically, the seed is generated from bits of data collected from the computer system, such as the clock, running processes, status registers, keystrokes, key press timing, and mouse movements, for example. System interrupt and event handling within different computer systems, however, may reduce the effective randomness of at least some of these seed sources.